package 力扣._994_腐烂的橘子;

import java.util.*;

public class Solution {
    public int orangesRotting(int[][] grid) {
        //从腐烂节点开始广度优先搜索，树的深度即是全部腐烂的最小时间
        //但题目没有说只有一个腐烂橘子，故要考虑多个腐烂节点的情况
        //建立一个队列列表，开始有几个腐烂橘子，就建几个队列，队列同时开始遍历,多点同时开始，短的覆盖长的
        List<Queue<Integer[]>> queues = new ArrayList<>();
        int[][] visited = new int[grid.length][grid[0].length]; //标记第几个访问，从1计数，0则未访问

        //寻找腐烂橘子
        boolean ishavedecay = false, ishavefresh = false;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    Queue<Integer[]> queue = new ArrayDeque<>();
                    Integer[] t = new Integer[2];
                    t[0] = i;
                    t[1] = j;
                    queue.add(t);
                    queues.add(queue);
                    visited[i][j] = 1;  //标记
                    ishavedecay = true;
                } else if (grid[i][j] == 1) {
                    ishavefresh = true;
                }
            }
        }
        if (!ishavefresh)    //没有新鲜橘子
            return 0;

        int max_time = 0;   //从1开始
        while (true) {

            for (Queue<Integer[]> queue : queues) {
                Integer[] decay = queue.poll();
                if (decay == null)
                    continue;
                int i = decay[0], j = decay[1], now = visited[i][j];
                max_time = Math.max(max_time, now);
                //将周围的好橘子入队,
                //上
                if (i - 1 >= 0 && grid[i - 1][j] == 1 && (visited[i - 1][j] == 0 || visited[i - 1][j] > now + 1)) {
                    queue.add(new Integer[]{i - 1, j});
                    visited[i - 1][j] = now + 1;
                }
                //下
                if (i + 1 < grid.length && grid[i + 1][j] == 1 && (visited[i + 1][j] == 0 || visited[i + 1][j] > now + 1)) {
                    queue.add(new Integer[]{i + 1, j});
                    visited[i + 1][j] = now + 1;
                }
                //左
                if (j - 1 >= 0 && grid[i][j - 1] == 1 && (visited[i][j - 1] == 0 || visited[i][j - 1] > now + 1)) {
                    queue.add(new Integer[]{i, j - 1});
                    visited[i][j - 1] = now + 1;
                }
                //右
                if (j + 1 < grid[0].length && grid[i][j + 1] == 1 && (visited[i][j + 1] == 0 || visited[i][j + 1] > now + 1)) {
                    queue.add(new Integer[]{i, j + 1});
                    visited[i][j + 1] = now + 1;
                }
            }
            //删除队列为空的队列，要使用迭代器
            Iterator<Queue<Integer[]>> iterator = queues.iterator();
            while (iterator.hasNext()) {
                Queue<Integer[]> queue = iterator.next();
                if (queue.isEmpty()) {
                    iterator.remove(); // 使用迭代器的 remove 方法进行删除操作
                }
            }
            if (queues.isEmpty())
                break;
        }
        //检查是否有孤立的未腐烂橘子
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j] == 0 && grid[i][j] == 1)
                    return -1;
            }
        }
        return max_time - 1;

    }

    public static void main(String[] args) {
//        int[][] grid = new int[][]{{2, 1, 1}, {0, 1, 1}, {1, 0, 1}};
//        int[][] grid = new int[][]{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
//        int[][] grid = new int[][]{{0, 2}};
//        int[][] grid = new int[][]{{0}};
//        int[][] grid = new int[][]{{1,0,2,2,2}};
        int[][] grid = new int[][]{{1, 1, 2, 2, 1, 2, 2, 1, 0, 2}, {0, 1, 2, 1, 0, 2, 2, 2, 2, 1}, {0, 0, 0, 0, 2, 0, 2, 0, 1, 1}, {1, 0, 1, 2, 0, 1, 0, 1, 1, 1}, {2, 1, 0, 0, 0, 2, 2, 1, 1, 1}, {0, 1, 2, 1, 1, 0, 2, 0, 1, 0}, {0, 2, 2, 2, 0, 1, 1, 2, 2, 1}};
        int i = new Solution().orangesRotting(grid);
        System.out.print(i);
    }
}
